>> Dr. Lanham:
This morning we continue our series on the Ancient Civilization of Greece, and I hope that you have been in previous sections, and sessions of our symposium, and if not, then you have the brochure that will lead you to several more this week. 

I think you still have something like 10 more opportunities to learn various aspects of this ancient culture.  

And it might serve you well in choosing a place to study abroad or to study but certainly welcome.  

I want to have Dr. Wafeek Wahby, the coordinator of this series to introduce our speakers today.  

>> Dr. Wahby:
Good Morning, and welcome to Ancient Greece Symposium, the long name of it, "A Futuristic Look Through Ancient Lenses".  

Last year we went as far back as ancient Egypt and this year with the natural progression to go to Greece, and I thank you all for coming, and thank Dr. Aulds for coming also, and being with us today, and I wanted to find a way to start this, and introduce our distinguished speakers, and I came up with a crazy idea. 

To start by saying, "I hate math." I am sure everybody has said that at one time, and Mommy would kind of say, "Why, darling, why?"  

Just I hate math. 

 No, it's easy like one, two, three.

 And that's difficult mommy, give me a break.  

Now, it doesn't make sense mommy. 

I hate math. 

No, what one plus one equals?

Audience, Math students?  

One plus one equals, and two plus two equals, so it is logical honey, I mean, why do you hate math?  

I hate it, I hate it, I hate it, I hate it, until this teacher came and was so thoughtful and understanding, and he just made it as simple as, and so I love math now.  

Well, it's not all Greek to me anymore, because I had a good teacher who was able to give it to me in such a good way that I will transfer to my kids and my students as well in the future, so math is not problems, not all Greek to me.  

Peter thank you very much for coming, thank you very much Bill for coming.  

And it's all yours now.  

>> Dr. Peter Andrews:
I'll thank you again for coming.  

That's us. 

I am Peter Andrews, the little guy, and the tall one is Bill Slough. 

We both are in the mathematics computer science department.  

And we want to talk a little bit about Euclid, probably the most famous of the Greek mathematicians, but certainly not the earliest.  

I always say to my students, there are about two or three things that everybody remembers from high school mathematics.  

And the first one actually appears in Euclid, it's written down in Euclid's elements, but it's not, it doesn't come from him, it's Pythagoras.  

So if I said what's the Pythagorean Theorem, what would you say? 

A squared plus B squared equals C Squared. 

Everybody remembers that. 

And it's written down in Euclid.  

So, let me, interestingly enough, if you look on page 9, of your program, this is very carefully orchestrated, and you’ll see a picture that says the school of Athens with Plato and Aristotle in the middle.  

Well this is the school of Athens, but that's not this copy right here, which is from Pierre-Fracois Cozzette, in the mid-eighteenth century. 

This is actually by Raphael, and it's one of four large Frescos in the Vatican, describing or illustrating ancient traditions, it's very much like, and there are supposedly Aristotle and Plato, the giants of Greek Philosophy. I don't imagine anything looked quite like this.  

And typical of renaissance Fresco, it's sort of a conglomeration of things. 

There are people that didn't live within two or three hundred years of each other all walking around lounging together and joking.  

But down in the bottom corner here, we are actually doing some mathematics, and in fact you can see, this is now it is actually not completely clear whether this was supposed to be obviously one of the great Greek geometers, and so there are two candidates, and nobody's completely sure who Rafael intended, one is Euclid and the other is Archimedes. 

But nonetheless, you know, there they are doing geometry, and I'll pass this around.  

This is a very nice sort of translation and collection of the most, one of the two most famous books in the entire western world, "Euclid's Elements". 

And on the front cover, you see an enlargement of precisely this piece here. 

And this author, of course, states without any qualification, it's Euclid.  

But I'll let you pass this around so you can have a look at that.  

And just to remind you of sort of how mind-bogglingly good the renaissance artists were, this is a Fresco, which means it is painted on wet plaster.  

So, you have to smooth on plaster, and you have to paint while it is still wet, so that the paint will soak in, so you can only paint little chunks at a time, because you can only paint what you can only plaster what you can get painted, and that they could put together things as brilliant as this, covering an entire wall, in these little plaster chunks is sort of mind-boggling.  

Anyway, this is sort of just a little artistic rendering showing how important Euclid and geometry was to the ancient world.  

Now, whether this is what Euclid should look like is hard to say, because nobody much knows what Euclid looks like, and here are a couple of other visions of Euclid. 

>> Dr. Bill Slough:
I am going to break in here just for a second.  

Because I think I am going to get a chance to talk later, but the calipers here are going to play a central role to things that we are going to see a little bit later today. 

>> Dr. Andrews:
So here are a couple of maybe Euclid really should have been bald, he's got a hat on there, so we really can't tell for sure, this is an old engraving, and then we've got a couple other images. 

This is from a hall with ancient philosophers and scientists, Euclid is one of them, he's got lot's of hair there, but maybe he was younger than Rafael's picture, who really knows, basically nobody knows much of anything about Euclid, sad to say.  

So, in some sense, when Bill and I were doing this, we thought we really should have just put up a blank slide here, because there literally is very little known. 

There are two Euclids mentioned in various places, and it's not even clear which one is the Euclid, so two born in Greece, what's pretty sure is that he lived around 300 BCE, and it's absolutely certain that he taught in Alexandria. 

So Alexandria was the great city founded by Alexander the Great, and was sort of because the center of Science and Learning in the Greek empire, so he certainly taught in Alexandria, under the reign of Ptolemy the First, and he certainly taught lots of mathematics, he wrote this magnificent book that heading it's way around, "The Elements", it actually comes in several books, instead of chapters, they are called books. 

It's not even clear how much of that Euclid actually did. 

For instance, the Pythagorean theorem which is clearly much earlier, and documented much earlier than Euclid is sitting there unattributed as right there in book two.  

As proposition something or other, right down. 

So how much of that is Euclid's and how much is Euclid writing down what other people had done?  

A rather unknown Greek mathematician Eudoxus, clearly a lot of geometry that ended up in the elements, and Euclid doesn't mention much at all. 

Archimedes who came slightly later than Euclid, credits Eudoxus with a lot of the things he did. [00:09:36;16]

It's not clear how much of the mathematics is his but it is crystal clear that he decided how to write things down.  

How to lay out axioms, prove theorems from axioms, the logical thinking, this implies this implied this implies this plus a tremendous number of instructions and one of which is what we are going to focus on here later today. 

So he did write some other books, one about "Optics”, so there's a little physics, that's light reflections, mirrors, prisms, and he actually wrote a book on music.  

Comments on Music, which is a lot of mathematical.  

This may be completely apocryphal, there's no way to tell whether he actually said this, but apparently the story is that when Ptolemy or one of the, probably Ptolemy the King, sort of wanted to know what he should do to master mathematics, and particularly geometry, and Euclid told them, "There's no royal road to geometry." 

The moral of the story is, you have to do your homework.  

Every night, after every class.  

So, I want you to take a look here at a couple of the versions, so Euclid wrote these down, The Elements down around 300 BC, and of course there is no printing press, things are written by hand.  

But he clearly wrote them out, but this is the oldest extant, certainly the oldest piece that has a diagram in it, and interestingly enough, this was discovered in an excavation in Greece, literally excavating a garbage dump, in an old town, they are doing an archeological dig, concentrating on the garbage pit, and they found this piece of papyrus, which includes clearly a diagram, and that's so it's hand written on Papyrus in Greek, and there's the diagram. 

 Now of course up until the printing press, that's the way things had to be reproduced. 

Somebody had to copy them out, paper technology got better but they had to be copied like this. 

So here's another one, this is the oldest complete, i won't say, maybe it's not completely the oldest, but it's pretty close. 

This is from the Bodleian Library in Oxford, and it's dated at about 888 CE, or 888 AD.  

It's interesting again, it's hand-written, so this is sort of written out here, this is the title page, and you’ll notice this is a cautionary tone. 

A note to you, that it's filled with these scribbling, this is somebody else, this is not the book.  

So, if you write in the margins and corners of your textbook, be careful what you write, because you never know, 1000 years later, that somebody might pop this up. 

And the nice thing is, there is a different library or sort of access to this, this copy where you can actually see every page, and there are actually indexed by the proposition of book.  

So here you can see again, there are scribblings in the margins, certainly a few scribblings over, up over here, but this is the book written out. 

And this is actually one of the propositions we are going to talk about.  

Book Seven Proposition one, and there are the figures laid out, it is certainly in Greek and something you'll this things laid out as Bill said with calipers we are going to see in a minute.  

Now, once you get a printing press, this is the first typeset edition from 1482 in Venice. 

A couple things, first of all, you actually have nice beautiful type, diagrams, and another thing you can see is, they don't make books like they used to.  

So, this is the I am not sure this is the actual title page, or the beginning page of a chapter, but this is written in Latin as opposed to Greek, and it's this ornate typeset here, and we've got another page I think from there later on.  

Again, you know, good clean pictures, who knows how good the pictures were in Euclid's original manuscript, we certainly saw the kind of crude picture in the papyrus.  

So, that's the first printed version, the printing press is about 1450ish, I think Gutenberg was probably around then, so it's not long after that where we get a printed version of The Elements. 

That's how important it was, as it was among the first books printed.  

Now here's the first English version, the first printed English version, maybe this is not the English version at all, certainly the                                first printed English version, the element of geometry of the most ancient philosopher Euclid.  

This claims that it's Euclid of Megara; I mentioned that there are two Euclids. 

And actually I think the current wisdom is that the Euclid that we are talking about is not Euclid of Megara, but that's not a huge, but this was printed by a man named John Davy, you see it down here in 1570.  

So, within roughly a hundred years of first version, which was in Latin, and of course, most scientific work was still written in Latin in 1570.  

Newton wrote in Latin, and he was significantly later than that, but this was an English version that people could read and study.  

This is a lot later, 1847, you know, a few hundred years later. 

It's interesting here because A.) It’s in color, not that there wasn't some color, but there's a lot of color in this, and it's an illustration of what a lot of people did with Euclid. 

They, instead of just simply transcribing exactly what he wrote down, they would write well, this is what he said, but here's what I think you should think about it.  

And the interesting thing about this, we'll look at a couple of pages here, the idea was this author, Oliver Burn, essentially replaced all of the proofs, he wrote down all of the propositions, and replaced everything else with his own illustrations.  

I am going to do it using colors and squares and blocks, and so this is his proof, instead of writing it out the way Euclid would have. 

And there are some other examples of that. 

So, you know, here's the statement, of an isosceles triangle, the internal angles of the base are equal, then the sides when produced, and he gets this, so if that's isosceles triangle, when you produce things, those are also equal, but this believe it or, I am sure you believe this is not the way Euclid did it.  

So this is an illustration, A.) It’s a beautiful book, and you know, a couple hundred years old, and it shows how central, how important the elements were because people kept trying to make them more popular, just like this is sort of the version of the calculus textbook now, that how text here, and a margin this big with fancy pretty colored pictures, trying to make it more accessible.  

>> Dr. Slough
As a side note, this was a commercial failure, so the publishing company basically went out of business, and at the time, they has 75 percent of the stock that they had published, went unsold. 

So whatever that's worth. 

>> Dr. Andrews:
They are probably not still on eBay.  

Now this, we probably won't go to the hot link, but just to show you where things have come, this is a from David Joyce, who is at Clark University, and he produced a sort of live version of Euclid, so almost all of the diagrams are actually little java applets that you can pull around and change to illustrate how things fit together.  

So, it's an actual transcription of all thirteen books, with all the illustrations kind of augmented by live versions, so it's just a continually ongoing study, and it's almost certainly true that the two most published and purchased books, in certainly the western world, are the Bible and Euclid.  

Euclid's Elements.  

And this book to show you, go on here, to show you how central it was to education, our own, of course how can you give a talk in Illinois, without Lincoln. 

But, Lincoln actually was convinced that learning Euclid was important.  

Learning Geometry and the arguments and the way Euclid presented things, was crucial to him becoming a good lawyer. 

So learning how to reason, and how to go from propositions or given facts to conclusions was important in him being able to argue both in politics and in law, and the first six books of Euclid form the Geometry, the heart of the geometry, and Lincoln even memorized them, but his goal was to be able to explain any proposition in the first six books of Euclid. 

So in this that's approximately 160 pages of pretty dense stuff, you know and educated by a lamplight in his little Kentucky cabin, this was his goal, and he taught himself.  

So, he really, that shows you how important Euclid and studying Euclid was to education through well into the 20th century.  

And I think it should be important now. 

Now, the first six books of geometry that's what you've seen, you've probably seen lots of proposition, even seen them written out in geometry books, in 10th grade geometry one, well, we are going to talk about is not Euclid's geometry, but number theory, so that starts in book seven, and so number theory is the study of integers, whole numbers, you have to remember here, that Euclid’s doing this without numbers, to some extent, without numerals.  

Nobody used 1,2,3,4 written out that way, until much later.  

If anything he might have used Roman numerals, but probably not even that. 

So, everything has to be done geometrically. 

And in spite of that he defined that that was a whole number, what's a prime number, what's a composite, all those things fairly clearly, what's a perfect number, some of you might have seen, in 1420, it's a number which is the some of it's divisors.  

And he actually proved a lot of very important results. 

This is in blue, because this is what we are going to talk about the rest of the time, the greatest common devisor of two whole numbers, but also he displayed the unique factorization theorem, a marvelous theorem, and his proof is basically still the proof that most use today.  

But there are an infinite number of primes and this is rather technical proof, but basically if two to a power minus one is prime, then you can get a perfect, this was in a study of perfect numbers. 

You can get (2 to the p-1)x(2 to the p-1) and that would have to be perfect.  

So that, a lot of pretty important results not being able to write down 27 as such on a piece of paper.  

So, lets see kind of how he did this.  

He did it basically geometrically, so one, whatever there, something magic, this is like a definition of a point, if you've ever seen sort of primal definition, you start with a unit, so there's some little measure somewhere, you set your calipers so you draw a little piece, that's your unit, and then a number is just what you can get by taking your caliper, so three means sort of the distance you get by setting off three ones.  

Five is five ones, and then this business about park and measuring is crucial to what we talk about divisibility, and factoring, basically two is this length here, and this length is six, so if I can lay off two and then another two, and another two, and completely fill up the six, then we'd say that two actually somehow measures six.  

And in our languages we'd say that two divides into six. 

So he's talking about what numbers are and what it means to divide numbers completely by laying them off in this notion of measuring.  

So, a prime number is one that's only divisible by itself and one, so there's nothing else that you can measure, so if this is our unit, you couldn't take two, because two and it wouldn't exactly fill up five, four obviously wouldn't fill up five, one is not enough and two is two much, so five is a prime.  

And relatively prime, that's going to be important to us here, relatively prime means there nothing that measures both of them, except one.  

One obviously measures all numbers, but two nicely measures four, it doesn't measure nine, because you've got this one left over.  

And take any other one, it doesn't work.  

Two doesn't, three doesn't, four doesn't and you're done.  

And here is his definition of a perfect number.  

P=the sum of its parts, well the things the parts, one measures six, two measures six, three measures six, we think of that as 1 divides 6, 2 divides in 6, 3 divides into 6, and if you add them all up, you get six.  

So that's the way he starts laying out with just this geometric idea, how we do arithmetic.  

Now this is Book Seven, Proposition one.  Book seven starts with a lot of definitions. But this is what it says.  So now it is time for a little interaction.  

We've been going here for you know, twenty minutes, plus, it's time to get involved.  

So you have around here, somebody is going to have to be manning, or a couple of people, but take a look at the, and those of you there can come up, we've got two unequal numbers being set out.  

Well, you've brown, you've got gold numbers, and then some other color.  

So what I want you to do is, from the gold ones, take out twelve, so there are piles of twenty, so take out twelve, and stick them together.  

And the other ones are in piles of 10 as well, I want you to take out 31 of them and make one great big long pile with 31 long. 

So now we got, if you've got them laid out here, what we've got here are two unequal numbers and then this is going to be crucial, so I want to, we are going to play here so we understand this, we want the less to be subtracted from the greater, so line up the orange with the other color, and subtract off what they match, and just pull off.  

Now which one is bigger?  

Now throw away the 10 or the 12 and take the bigger piece, now you've got an orange and a non orange, and I want the bigger of the ones that don't match, so, here I want, so I subtracted that, I threw that away, whoa, and there ok?  

And now take the smaller and subtract it from the larger again.  

And remove that piece, no, remove that piece. 

Ok, you'll find now yeah, so oh, do that again? 

One two three, four, five, six, seven, oh there should have been twelve, there was your twelve.  

Oh, we lost a little bit.  

Now then, you'll find the odd colored one is smaller, so you subtract, you line it up with the orange, and throw away the orange piece that matches, alright subtracting that, and now the orange piece is smaller again, so you align it up and throw away the piece there, throw away the matching piece. So subtract the smaller from the larger.  

You should be down to two and five, now. So take the smaller one, which is now the off color, and subtract it and throw that away.  

And you should be able to do it again, so we are just continually subtracting the smaller from the larger, all right, until a unit is left, so we get down to where one single one is left, all right.  

If you get there, if you get down to a unit left, then those are prime to each other.  

That's the proposition.  

We are not going to go through the proof, but I wanted you to see the idea of continually subtracting the smaller from the larger, and I wanted to make sure you were still awake.  

So, but that's the idea.  

We are going to see this again. 

We are going to subtract the smaller from the larger, and when that, when what's left over gets smaller, we are going to switch and subtract that.  

And that's this idea in Euclid's proposition, if you do this, and get down to one, then they were relatively prime. 

Now, what were my two numbers?  12 and 31.  

Well what divides into twelve?  

2, 3, 4, and 6 and 12, if you want. 

Thirty-one is actually prime. 

Nothing divides into 31. 

So there's nothing that divides into both.  

So they have no common factors, and that's how you verify you have no common factors. 

That's one way to verify it.  

By and also that idea of successive subtractions.  

So let's look at an example here and then I will be quiet and man the machine.  

So let's, this is doing exactly, but it would have been a little hard to stretch out 140 black unifix cubes, so you start with 140 and 33. 

You subtract the smaller and the smaller, and the smaller, and the smaller, and now what's left over is 8.  

So eight is now the smaller, so we switch them over, that was when you changed colors, and now we subtract eight, once, twice, three times, four times, and now, we are down to one left over.  

So if we get down to a unit, then those things are relatively prime. 

So that's the idea just with subtraction.  

Of course Euclid couldn't actually not have done this, because he didn't write 25 and 8 like that, but he certainly had the idea, and knew what was going on.  

And if you check it out, the only things that divide into 33 are 3 and 11, and what divides in here, this is two times seventy, so it is 2 x 2 x 5 x 7, and none of those are 11 and 3, so no common divisors.  

So that's the basic idea of things relatively prime, and this idea of subtracting and then Euclid is going to actually leverage that idea into something even more interesting.  

>> Dr. Slough:
I think I'll just stay here. 

>> Dr. Andrews:
All right, I'll just go over here then.

>> Dr. Slough:
Ok, so that's the idea of relatively prime. 

Now we want to ramp things up just a little bit, but not much, so again, we start with two numbers, two whole numbers, in this case 1035 and 759 and using the language of Euclid, we are looking for a common measure, which today we call it a common divisor, but we want the greatest common measure, or today's language, the greatest common divisor.  

So, lets just think about this for a second. 

So let's forget Euclid. Just try some things. 

Well, how about 3?  

Is three a divisor of both? 

Well, sure enough. 

So that's a candidate for an answer. 

If you wanted to take this back a little bit, you could say well how about one?  

Should one be an answer? 

Because one divides anything, so one is certainly common, but is it the biggest? 

No, three is bigger; can you find one that is bigger yet?  

Well, with a little bit of work, it's not hard to see that 23 divides both of them, so there's a bigger candidate for the answer.  

Is that the biggest one though?  

Well, no. 

So you can find one bigger, 69, divides both of them.  

Is that the biggest one?  

Well, I can't say without a little bit of effort, but it turns out that it is, and one way to see that it is, is to produce the factorization, prime factorization of each of them, so 3 x 3 x 5 x 23 that product is 1035, 759 same thing, takes a little bit of work, this would take, I said a little bit of work, but I need to tell you that my background is computer science, and for computer science, these numbers aren't even worth thinking about.  

These are too small.  

So the kinds of numbers that we sometimes think about they've got thousands of digits. 

Now if you take a number that's got a thousand digits, and try this sometime when you are bored, and try to factor that number, you are going to have a hard time doing that, unless that number is a very special, you've chose it very specially, but just pick a random 1000 digit number, you are going to have a hard time factoring that. 

And when I say you, it's not just you, because computers would have a hard time doing the same thing. 

It would take them a long, I mean, a computer could do it, but it would take a long time.  

So, the idea here is, it goes a little bit beyond the mathematics, because we don't want necessarily just the answer, but we want to be able to get it quickly without too much work, whatever "too much" might mean.  

So, as we like to say in math, it turns out that this is a horrible idea to get the answer, if you are interested in efficiency, just factoring.  

So, again, let's ignore Euclid and just try this ourselves, you might think that we are a little smarter than Euclid.  

Here's a way, a horrible way, it turns out, look at the answer, but not anytime too soon. 

Again, imagine that these two numbers are a thousand digits each. SO here’s my silly way of doing this.  

So you take the smaller of the 2, and you think to yourself, well, maybe this is the answer.  

It certainly couldn't be any bigger than that number. 

Let's take two small numbers, so if I said 18 and 39, the answer can't be any bigger than 18, the smaller of the two, because if I tried to get anything bigger than 18, it wouldn't divide 18, itself. 

So, that's the biggest it could be. 

And then I just sort of worked my way down, and then looking for the first one that I find that divides both. 

That will certainly work, in every sense of the word, if it's correct, but it's almost an exaggeration to say this is very labor intensive. 

That's an over-simplification.  

So, why should we ignore Euclid? 

He's a smart guy, so let's go back and see what he had to say. 

Now this is exactly, on this slide, this is exactly what Peter was telling us, it's just expressed in the modern language.  

So, GCD (Greatest Common Divisor) GCD of X and Y, so there's two a pair of two numbers, and if X is the bigger of the 2, then what you do is you just subtract and you are left with a slightly simpler problem.  

Simpler in the sense that at least one of the numbers got smaller, which is what you did just a few minutes ago.  

Now the word that strikes fear into every mathematics student, a proof, and for reasons of time, I am actually, you can thank me later, I am actually not going to go through this proof, but I will just say that's it's actually among all proofs, it's among the simpler proofs, and if I just gave you this hint and perhaps a little bit more, I think you could come up with this on your own.  

So, why are those two numbers equal?  

The basic ideas is you want to show that you've got two numbers that are equal, while each is less than or equal to the other.  

And if you can show that both ways, then they have, the only way that both of those facts could exist, is if the two numbers are the same.  

Ok, so, as we sometimes see in mathematics, that's left to the reader, left to the reader, that's for you to do.  

Now it's actually here, but like I said, I am going to skip it, you can thank me now or thank me later, so let's just quickly skip that.  

And here's this same modern statement of Euclid's idea, two numbers X and Y, take the smaller, subtract it from the larger, and throw away the larger, and what you are left with is (turns out) the answer to that simpler problem is the same as the answer to your original problem. 

That's an idea that pervades a lot of mathematics, you take one problem and you turn it into something that's simpler in some sense and you work down the simpler problem. 

The great thing about this is it just keeps iterating that idea.  Keep turning it into a simpler and simpler problem.  

So, if you believe that, and we haven't really given you a reason to believe it, but Euclid proved it, and I skipped it, but it's probably the world’s simplest algorithm method to carry out, so if you know how to subtract, and you know how to compare two numbers, anybody can do this, including a computer.  
Computers are good at comparing two numbers and they are certainly good at subtracting, and everyone in this room could easily do this. 

Even for a thousand digit numbers. 

Well you'd get tired of doing it, but you could do it in principle. SO here's the same sort of thing we did before, subtract, now, the X column I am always making sure I put the bigger number, so if the subtraction turns out to disrupt that order, then I'll just flip them around.  

Subtract, subtract, now again, I disrupted the order, so let's put it back so that I've got the biggest one in the X column, subtract, again, the order is disrupted, slide out, subtract, subtract, now you could stop here according to Euclid and he would recognize that 69 measures 69 and there's your answer, 69 must the greater common measure or the greatest common divisor of that original pair.  

If you didn’t recognize that, you could always subtract and you get to zero, you'd better stop.  

So, that's it.  

Now, that of course takes advantage of what we know about numbers and arithmetic, which that is as Dr. Andrews said, wasn’t available to Euclid, so here's essentially the same thing you did with the manipulatives.  

At pretty much as Euclid would do it. 

So, here is just a small example, 30 and 21, so I've measured out on the left, 30 units, that's to the right of that, 21 units, and what do we do?  

We have to subtract, but how do you subtract? 

See, you get your calipers from that painting that we saw, and you mark it off. So there's one, and you try to mark it off the second time, what happens? It doesn't fit.  So you've got a piece left over. 

Now, what happens? 

You take the left over piece, and you move it off, and so this left over piece is exactly this left over piece, and then you just slide this over.  

So that's one application of what we today would call Euclid's rule.  

And so now I've got two pairs of numbers, this pair and this pair, and Euclid would say the answer to the question we have in mind, is exactly the same. 

Doesn't matter which one you pick, this one or this one.  

Well, why wouldn't you pick the one on the right, it's simpler?  

And if you wanted to put numbers to the blacks of course, it's not hard to do. 

What have we got here? 

We've got on the right we've got the 21 that we started with, and then this is the leftover piece, 30 minus 21, 9.  

And do it again, so you measure you measure and there's leftover piece.  

And you take the leftover piece, and you lop it off, and move it over there with the other length, and now we've got three pairs, and according to Euclid, all three of them have the same answer.  

Same greatest common divisor.  

So, you get to pick, which one would you like to work on?  

Well, of course you want to take the simplest one. 

Simple means smaller. 

 So you measure once, twice, three times and it fits exactly, and when it fits exactly you are done.  

So the small one measures the big one, and in this case, three times, and this isn't the proof of anything but just for fun, let's put the original two numbers up there, and lets' at least make sure that this is the answer.  

That better measure each of them.  

This doesn't prove that it's the biggest measure, but at least it better measure, and sure enough you mark it out and you can see that it does.  

Ok, now, you can take that idea and this idea of measuring, measuring off so many times, why keep subtracting, why not just do it in one operation and be done with it? 

So, repeated subtraction, as I think everyone here knows, is just, I call it forth grade division.  

I don't know if that is really accurate, could be third grade, where did we learn that?  

Quotient the remainder is basically what we are talking about.  

So, here's the same idea expressed in modern notation that essentially comes from Euclid. 

So if you have an original pair of numbers, x,y and you want the greatest common measure, greatest common divisor, what you can do is you can make a simpler problem by doing not subtraction any more, that's too much work, let's just do one division, so this is the modern notation that perhaps some of you have seen before, (X mod y) what that means is you divide x by y and you take the remainder, just like we did in well, I'm going to say, 4th grade. 

But it might be third grade where you went to school.  

And of course it doesn't matter which way you arrange them here, whether it's this way, or the other way around, it's exactly the same, and let see an example of this.  

So, you could do this the old way that I showed you, subtract, subtract, and so forth, but let's use our newfound knowledge.  

So we do division.  

1035 divided by 759, so again you can think of this geometrically, take this line segment of 1035, measure off 759, how many do you get? 

Goes in once, we would say in 4th grade, right?  

It goes once, with a remainder of 276.  

Now what happens? 

Look at this. 

So it says, take the second one, slide if over into the first position, so the 759 should come to the x column, what goes here? 

According to Euclid, the remainder, and the remainder was 276, so we now, you can predict as well as I can show you 759 is going to come down, 276 will appear in the y column.  

But again, now you've got 2 lengths, 759, 276. 

Take your calipers, mark off 276 as many times as you can, any fourth grader will tell you with a little prodding, that that goes in twice, with a remainder of 207.  

What happens next?  

276 slides down, the remainder fills in the gap.  276, 207 do it again.  

Divide, division is pretty simple.  So, 207 slides down, the remainder comes into place. 

Do it again. 

This time, 69 measures to 207 exactly three times in fact, and so you could either stop there and realize that it measures it, or you could just go ahead and do it, and as soon as you get to a remainder of zero, there's you answer.  

This is the algorithm that basically Euclid gave is in what is called Proposition Two, so Book Seven, Proposition One, talks about two numbers that are relatively prime, and how to determine that. 

Proposition two, gives us this, and in case you are not sufficiently impressed, let me say it for you.  

This fantastic method and it's fantastic for a number of reasons, well, first of all you have to be kind of interested in finding the greatest common divisor, assuming that is the case, this is fantastic, because if you know how to divide, it turns out that this not only gives you the correct answer, but it gives you the answer in a I'm going to say relatively small amount of work.  

Relatively few numbers of divisions.  

Donald Canuth, who is sort of the modern day founder of this study of algorithms, basically has told us that this really is among the world’s oldest algorithms that we know about.  

If you wanted to, and it's not hard, and I won't go through the details, it wouldn't be hard to write a computer program to basically automate what I just showed you.  

This is an exact transcription of one version of a computer program that would do that, and if you look, even if you know nothing about computer programming, you can look at this, and you can look at the modern day transcription of Euclid, and you can just see how similar things are.  

Look at this, return GCD, Y, this looks kind of bizarre, X%Y, but in computer language, java, that simply means 4th grade division, give me the remainder.  

Fast forward to the 1800' and there was a French I think he was a mechanical engineer, and he basically said, now wait a second, I know about this method for finding this Greatest Common Divisor, but he stated in a much more precise way than I did just a minute, just how good this is. And it basically, what's important is this part right here.  

It takes at most 5k steps, and what is k? 

K is the number of digits involved, and if you think back to the problem that I was telling you about, k is what? 

Well, for all of the simple examples, K is, what did we do? 

Four, we had a four digit number I think, three digit number, but the kinds of numbers that people that study algorithms would be interested in, is today, 1,000, 2000, maybe a million, so think, just think how good this really is, what this is telling us. 

If we had two numbers that are roughly on the scale of a million each, in the millions, so K is what? 6? 

So roughly in a handful of steps, 5 x 6, you can get the answer.  

So think back to that what I called brute force method, just think how hard that would be relatively speaking, if I took two numbers in their millions, and I say, well, let's start at the top and work my way down, I am going to be here all day, and that same idea applies to computers, you can get a computer, if you can provide a computer with an algorithm that has a relatively small number of steps, that means you can get the answer quickly.  

Ok, so that was the 1800's, now I am going to take you fast forward through a couple more centuries.  

I am going to skip, basically skip over a lot of details here, and you can thank me later. 

This isn't hard, what I am skipping over, but it's more than what we want to do today.  

So this is not Euclid, this is again, a result from the French mathematician in the 1800's so quite a few centuries have gone by, but basically the claim is that you can take this pair, x and y, you can find the greatest common divisor, d, but not only that, you can find this other pair of numbers, kind of magical, that when you combine them in this way, it adds up to the greatest common divisor. 

And as we like to say in mathematics, sometimes, "it turns out" that to find those somewhat magical numbers, is not that far removed from doing what Euclid said. 

So basically take the same kind of table, you expand it a little bit, and you get this nice result.  

I say it's nice, because it turns out to have a very practical application.  

And fast forward another couple centuries, and you find that people are quite interested in the Internet these days, and people like to communicate on the Internet, but not everything is intended to be public.  

So, for example, if I make a purchase on the Internet, and I type in my credit card number, I kind of like to believe that that credit card number isn't being seen by the entire world.  

Well, in the late 1970's now it took three computer scientists to come up with this idea, but it got this, what I think, most people would say, this clever idea and it all goes back to Euclid.  

And it's a question of if I send some information over the internet, and maybe someone is in some sense "listening" they can see what I am sending, I want to send it in a way that even if someone else saw it, it would just look like gibberish. 

So that's the idea of today what we call encryption. 

So I, it's like sending a secret message back when you were in the third grade. 

You had your cracker Jacks decoder ring, and your friend had the same decoder ring, and you would send this secret message.  

It's the same kind of thing except that if you do this in a cracker jack's way, and you send the message like your credit card number over the internet, that's not so good, because everybody knows about the cracker jacks and the decoder ring, and with little trouble you can figure it out.  

So that's not good. 

So you need a way to send something that looks like gibberish that on the other end somebody else can decode, so there's basically two kinds of things going on here, encryption, taking good stuff and turning it into gibberish, and decryption, taking the gibberish and turning it back into what it started. 

So, I could talk for an hour more at least, probably two hours, just on this slide, but I am not going to do that, but I do want to just mention that there's a key component to how all this works, is mathematical and it relies on this extended Euclid algorithm. 

There's also this other idea, which isn't completely related to Euclid other than the fact that of course he kicked off the study of prime numbers, which for many years, people thought that was just an amusing mathematical recreational kind of thing right? 

Who cares about prime numbers?  

Well, it turns out this is a prime example, it turns out that prime numbers have practical applications, and this is one of them.  

So, a couple of things here.  

Go back to Euclid.  

Number one, prime numbers, number two, and this idea of finding the greatest common divisor.  

So, even though I didn't pick the title of this symposium, I think it was a perfect match to Euclid through the centuries, going all the way back to roughly 300 BCE, to essentially today, and it all sort of of hangs together in a rather nice way, and so these things that we see now in books that you might be tempted to say, oh well, this is an interesting recreational thing, but it is not good for anything, you'd be surprised.  

So, hats off the Euclid.

[Applause]

>> Dr. Wahby:
And hats off to our distinguished speakers and we have other classes to go to, but if you have a question about anything this morning, you can ask of our speakers, otherwise, go in peace and see you next time. 
>> Dr. Lanham:
This morning we continue our series on the Ancient Civilization of Greece, and I hope that you have been in previous sections, and sessions of our symposium, and if not, then you have the brochure that will lead you to several more this week. I think you still have something like 10 more opportunities to learn various aspects of this ancient culture.  And it might serve you well in choosing a place to study abroad or to study but certainly welcome.  I want to have Dr. Wafeek Wahby, the coordinator of this series to introduce our speakers today.  

>> Dr. Wahby:
Good Morning, and welcome to Ancient Greece Symposium, the long name of it, "A Futuristic Look Through Ancient Lenses".  Last year we went as far back as ancient Egypt and this year with the natural progression to go to Greece, and I thank you all for coming, and thank Dr. Aulds for coming also, and being with us today, and I wanted to find a way to start this, and introduce our distinguished speakers, and I came up with a crazy idea. To say by saying, "I hate math." I am sure everybody has said that at one time, and Mommy would kind of say, "Why, darling, why?"  Just I hate math.  No, it's easy like one, two, three. And that's difficult mommy, give me a break.  Now, it doesn't make sense mommy. I hate math. No, what one plus one equals? Audience, Math students?  One plus one equals, and two plus two equals, so it is logical honey, I mean, why do you hate math?  I hate it, I hate it, I hate it, I hate it, until this teacher came and was so thoughtful and understanding, and he just made it as simple as, and so I love math now.  Well, it's not all Greek to me anymore, because I had a good teacher who was able to give it to me in such a good way that I will transfer to my kids and my students as well in the future, so math is not problems, not all greek to me.  Peter thank you very much for coming, thank you very much Bill for coming.  And it's all yours now.  

>> Dr. Peter Andrews:
I'll thank you again for coming.  That's us.  I am Peter Andrews, the little guy, and the tall one is Bill Slough. We both are in the mathematics computer science department.  And we want to talk a little bit about Euclid. Probably the most famous of the Greek mathematicians, but certainly not the earliest.  I always say to my students, there are about two or three things that everybody remembers from high school mathematics.  And the first one actually appears in Euclid, it's written down in Euclid's elements, but it's not, it doesn't come from him, it's Plathagorus.  SO if I said what's the Plathorum therum, what would you say? A squared plus B squared equals C Squared. Everybody remembers that. And it's written down in Euclid.  So, let me, interestingly enough, if you look on page 9, of your program, this is very carefully orchestrated, you'll see a picture that says the school of athens with Plato and Aristotle in the middle.  Well this is the school of Athens, but that's not this copy right here, which is from Pierre-Fracois Cozzette, in the mid-eighteenth century. THis is actually by Rapheal, and it's one of four large Frescos in the Vatican, describing or illustrating ancient traditions, it's very much like, and there are supposedly Aristotle and Plato, the giants of Greek Philosophy. I don't imagine anything looked quite like this.  And typical of renaissanceFresco, it's sort of a conglomeration of things. There are people that didn't live within two or three hundred years of each other all walking around lounging and joking.  But down in the bottom corner here, we are actually doing some mathematics, and in fact you can see, this is now it is actually not completely clear whether this was supposed to be obviously one of the great geometers, and so there are two candidates, and nobody's completely sure who Rafael intended, one is Euclid and the other is Archimedes. But nonetheless, you know, there they are doing geometry, and I'll pass this around.  This is a very nice sort of translation and collection of the most, one of the two most famous books in the entire western world, "Euclid's Elements".  And on the front cover, you see an enlargement of precisely this piece here. And this author, of course, states without any qualification, it's Euclid.  But I'll let you pass this around so you can have a look at that.  And just to remind you of sort of how mind-bogglingly good the renaissance artists were, this is a Fresco, which means it is painted on wet plaster.  So, you have to smooth on plaster, and you have to paint while it is still wet, so that the paint will soak in, so you can only paint little chunks at a time, because you can only paint what you can only plaster what you can get painted, and that they could put together things as brilliant as this, covering an entire wall, in these little plaster chunks is sort of mind-boggling.  Anyway, this is sort of just a little artistic rendering showing how important Euclid and geometry was to the ancient world.  Now, whether this is what Euclid should look like is hard to say, because nobody much knows what Euclid looks like, and here are a couple of other visions of Euclid. 

>> Dr. Bill Slough:
I am going to break in here just for a second.  Because I think I am going to get a chance to talk later, but the calipers here are going to play a central role to things that we are going to see a little bit later today. 

>> Dr. Andrews:
So here are a couple of maybe Euclid really should have been bald, he's got a hat on there, so we really can't tell for sure, this is an old engraving, and then we've got a couple other images. This is from a hall with ancient philosophers and scientists, Euclid is one of them, he's got lot's ofhair there, but maybe he was younger than Rafael's picture, who really knows, basically nobody knows much of anything about Euclid, sad to say.  So, in some sense, when Bill and I were doing this, we thought we really should have just put up a blank slide here, because there literally is very little known. There is two Euclids mentioned in various places, and it's not even clear which one is the Euclid, so two born in Greece, what's pretty sure is that he lived around 300 BCE, and it's absolutely certain that he taught in Alexandria. So alexandria was the great city founded by Alexander the Great, and was sort of because the center of Science and learning inthe Greek empire, so he certainly taught in Alexandria, under the reight of Ptolemy the First, and he certainly taught lots of mathematics, he wrote this magnicificent book that heading it's way around, "The Element", it actually comes in several books, instead of chapters, they are called books. It's not even clear how much of that Euclid actually did. For instance, the Plagorium Therom which is clearly much earlier, and documented much earlier than Euclid is sitting there unattributed as right there in book two.  As proposition something or other, right down. So how much of that is Euclid's and how much is Euclid writing down what other people had done?  A rather unknown great mathematician Doxxas, clearly a lot of geometry that ended up in the elelments, and Euclid doesn't mention much at all. Archimedes who came slightly later than Euclid, credits Doxxas with a lot of the things he did. [00:09:36;16]It's not clear how much of the mathemathics is his but it is crystal clear that he decided how to write things down.  How to lay out axioms, prove theroms from axioms, the logical thinking, this implies this implied this implies this plus a tremendous number of instructions and one of which is what we are going to focus on here later today. So he did write some other books, one about "Optics" , so there's a little physics, that's light reflections, mirrors, prisms, and he actually wrote a book on music.  Music, which is a lot of mathematical.  This may be completely aprocophal, there's no way to tell whether he actually said this, but apparently the story is that when Ptolemy or one of the, probably Ptolemy the King, sort of wanted to know what he should do to master mathematics, and particularly geometry, and Euclid told them, "There's no royal road to geometry." The moral of the story is, you have to do your homework.  Every night, after every class.  So, I want you to take a look here at a couple of the versions, so Euclid wrote these down, the elements down around 300 BC, and of course there is no printing press, things are written by hand.  But he clearly wrote them out, but this is the oldest extant, certainly the oldest piece that has a diagram in it, and interestingly enough, this was discovered in an excavation in Greece, literally excavating a garbage dump, in an old town, they are doing an archeological dig, concentrating on the garbage pit, and they found this piece of papyrus, which includes clearly a diagram, and that's so it's hand written on Papyrus in greek, and there's the diagram.  Now of course up until the printing press, that's the way things had to be reproduced. Somebody had to copy them out, paper technology got better but they had to be copied like this. So here's another one, this is the oldest complete, i won't say, maybe it's not completely the oldest, but it's pretty close.  This is from the [unclear dialogue] library in Oxford, and it's dated at about 888 CE, or 888 AD.  It's interesting again, it's hand-written, so this is sort of written out here, this is the title page, and you'lll notice this is a cautionary tone. A note to you, that it's filled with these scribblings, this is somebody else, this is not the book.  SO, if you write in the margins and corners of your textbook, be careful what you write, because you never know, 1000 years later, that somebody might pop this up. And the nice thing is, there is a different library or sort of access to this, this copy where you can actually see every page, and there are actually indexed by the proposition of book.  So here you can see again, there are scribblings in the margins, certainly a few scribblings over, up over here, but this is the book written out. And this is actually one of the propositions we are going to talk about.  Book Seven Proposition one, and there are the figures laid out, it is certainly in Greek and something you'll this things laid out as Bill said with calipers we are going to see in a minute.  Now, once you get a printing press, this is the first typeset edition from 1482 in Venice. A couple things, first of all, you actually have nice beautiful type, diagrams, and another thing you can see is, they don't make books like they used to.  So, this is the I am not sure this is the actual title page, or the beginning page of a chapter, but this is written in latin as opposed to greek, and it's this ornate typeset here, and we've got another page I think from there later on.  Again, you know, good clean pictures, who knows how good the pictures were in Euclid's original manuscript, we certainly saw the kind of crude picture in the papyrus.  So, that's the first printed version, the printing press is  about 1450ish, I think Gutenberg was probably around then, so it's not long after that where we get a printed version of the elements. That's how important it was, as it was among the first books printed.  Now here's the first English version, the first printed English version,  maybe this is not the English version at all, first printed English version, the element of geometry of the most ancient philosopher Euclid.  This claims that it's Euclid of McGarra, I mentioned that there are two euclids. And actually I think the current wisdom is that the Euclid that we are talking about is not Euclid of McGarra, but that's not a huge, but this was printed by a man named John Davy, you see it down here in 1570.  So, within roughly a hundred years of first version which was in Latin, and of course, most scientific work was still written in Latin in 1570.  Newton wrote in Latin, and he was significantly later than that, but this was an English version that people could read and study.  

This is a lot later, 1847, you know, a few hundred years later. It's interesting here because A.) it's in color, not that there wasn't some color, but there's a lot of color in this, and it's an illustration of what a lot of people did with Euclid. THey, instead of just simply transcribing exactly what he wrote down, they would write well, this is what he said, but here's what I think you should think about it.  And the interesting thing about this, we'll look at a couple of pages here, the idea was this author, Oliver Burn, essentially replaced all of the proofs, he wrote down all of the propositions, and replaced everything else with his own illustrations.  I am going to do it using colors and squares and blocks, and so this is his proof, instead of writing it out the way Euclid would have. And there are some other examples of that. So, you know, here's the statement, of an isocoles triangle, the internal angles of the base are equal, then the sides when produced, and he gets this, so if that's icosoles triangle, when you produce things, those are also equal, but this believe it or, I am sure you believe this is not the way Euclid did it.  So this is an illustration, A.) it's a beautiful book, and you know, a couple hundred years old, and it shows how central, how important the elements were because people kept trying to make them more popular, just like this is sort of the version of the calculus textbook now, that how text here, and a margin this big with fancy pretty colored pictures, trying to make it more accessible.  

>> Dr. Slough
As a side note, this was a commercial failure, so the publishing company basically went out of business, and at the time, they has 75 percent of the stock that they had published, went unsold. So whatever that's worth. 

>> Dr. Andrews:
They are probably not still on ebay.  Now this, we probably won't go to the hot link, but just to show you where things have come, this is a from David Joyce, who is at Clark University, and he produced a sort of live version of Euclid, so almost all of the diagrams are actually little java applets that you can pull around and change to illustrate how things fit together.  So, it's an actual transcription of all thirteen books, with all the illustrations kind of augmented by live versions, so it's just a continually ongoing study, and it's almost certainly true that the two most published and purchased books, in certainly the western world, are the Bible and Euclid.  Euclid's Elements.  And this book to show you, go on here, to show you how central it was to education, our own, of course how can you give a talk in Illinois, without Lincoln. But, Lincoln actually was convinced that learning Euclid was important.  Learning Geometry and the arguments and the way Euclid presented things, was crucial to him becoming a good lawyer. So learning how to reason, and how to go from propositions or given facts to conclusions was important in him being able to argue both in politics and in law, and the first six books of Euclid for the Geometry, the heart of the geometry, and Lincoln even memorized them, but his goal was to be able to explain any proposition in the first six books of Euclid. So in this That's approximately 160 pages of pretty dense stuff, you know and educated by a lamplight in his little Kentucky cabin, this was his goal, and he taught himself.  So, he really, that shows you how important Euclid and studying Euclid was to education through well into the 20th century.  And I think it should be important now.  Now, the first six books of geometry that's what you've seen, you've probably seen lots of proposition, even seen them written out in geometry books, in 10th grade geometry one, well, we are going to talk about is not Euclid's geometry, but number theory, so that starts in book seven, and so number theory is the study of integers, whole numbers, you have to remember here, that euclid's doing this without numbers, to some extent, without numerals.  Nobody used 1,2,3,4 written out that way, until much later.  If anything he might have used roman numerals, but probably not even that. So, everything has to be done geometrically. And in spite of that he defined that that was a whole number, what's a prime number, what's a composite, all those things fairly clearly, what's a perfect number, some of you might have seen, in 1420, it's a number which is the some of it's divisors.  And he actually proved a lot of very important results. This is in blue, because this is what we are going to talk about the rest of the time, the greatest common devisor of two whole numbers, but also he displayed the unique factorization therom, a marvelous therom, and his proof is basically the proof that most use today.  But there are an infinite number of primes and this is rather techincal proof, but basically if two to a power minus one is prime, then you can get a perfect, this was in a study of perfect numbers. You can get p-1x2 p-1 and that would have to be perfect.  So that, a lot of pretty important results not being able to write down 27 as such on a piece of paper.  So, lets see kind of how he did this.  He did it basically geometrically, so one, whatever there, something magic, this is like a definition of a point, if you've ever seen sort of primal definition, you start with a unit, so there's some little measure somewhere, you set your calipers so you draw a little piece, that's your unit, and then a number is just what you can get by taking your caliper, so three means sort of the distance you get by setting off three ones.  Five is five ones, and then this business about park and measuring is crucial to what we talk about divisibility, and factoring, basically two is  this length here, and this length is six, so if I can lay off two and then another two, and another two, and completely fill up the six, then we'd say that two actually somehow measures six.  And in our languages we'd say that two divides into six.  So he's talking about what numbers are and what it means to divide numbers completely by laying them off in this notion of measuring.  So, a prime number is one that's only divisible by itself and one, so there's nothing else that you can measure, so if this is our unit, you couldn't take two, because two and it wouldn't exactly fill up five, four obviously wouldn't fill up five, one is not enough and two is two much, so five is a prime.  And relatively prime, that's going to be important to us here, relatively prime means there nothing that measures both of them, except one.  One obviously measures all numbers, but two nicely measures four, it doesn't measure nine, because you've got this one left over.  And take any other one, it doesn't work.  Two doesn't, three doesn't, four doesn't and you're done.  And here is his definition of a perfect number.  P=the sum of its parts, well the things the parts, one measures six, two measures six, three measures six, we think of that as 1 divides 6, 2 divides in 6, 3 divides into 6, and if you add them all up, you get six.  So that's the way he starts laying out with just this geometric idea, how we do arithmetic.  NOw this is Book Seven, Proposition one.  BOok seven starts with a lot of definitions. But this is what it says.  So now it is time for a little interaction.  We've been going here for you know, twenty minutes, plus, it's time to get involved.  So you have around here, somebody is going to have to be manning, or a couple of people, but take a look at the, and those of you there can come up, we've got two unequal numbers being set out.  Well, you've brown, you've got gold numbers, and then some other color.  So what I want you to do is, from the gold ones, take out twelve, so there are piles of twenty, so take out twelve, and stick them together.  and the the other ones are in piles of 10 as well, I want you to take out 31 of them and make one great big long pile with 31 long. So now we got, if you've got them laid out here, what we've got here are two unequal numbers and then this is going to be crucial, so I want to, we are going to play here so we understand this, we want the less to be subtracted from the greater, so line up the orange with the other color, and subtract off what they match, and just pull off.  Now which one is bigger?  Now throw away the 10 or the 12 and take the bigger piece, now you've got an orange and a non orange, and I want the bigger of the ones that don't match, so, here I want, so I subtracted that, I threw that away, whoa, and there ok?  And now take the smaller and subtract it from the larger again.  And remove that piece, no, remove that piece. Ok, you'll find now yeah, so oh, do that again? One two three, four, five, six, seven, oh there should have been twelve, there was your twelve.  Oh, we lost a little bit.  Now then, you'll find the odd colored one is smaller, so you subtract, you line it up with the orange, and throw away the orange piece that matches, alright subtracting that, and now the orange piece is smaller again, so you align it up and throw away the piece there, throw away the matching piece. So subtract the smaller from the larger.  YOu should be down to two and five, now. So take the smaller one, which is now the off color, and subtract it and throw that away.  And you should be able to do it again, so we are just continually subtracting the smaller from the larger, all right, until a unit is left, so we get down to where one single one is left, all right.  If you get there, if you get down to a unit left, then those are prime to each other.  That's the proposition.  We are not going to go through the proof, but I wanted you to see the idea of continually subtracting the smaller from the larger, and I wanted to make sure you were still awake.  So, but that's the idea.  WE are going to see this again. We are going to subtract the smaller from the larger, and when that, when what's left over gets smaller, we are going to switch and subtract that.  And that's this idea in Euclid's proposition, if you do this, and get down to one, then they were relatively prime. Now, what were my two numbers?  12 and 31.  Well what divides into twelve?  2, 3, 4, and 6 and 12, if you want. Thirty one is actually prime. Nothing divides into 31. So there's nothing that divides into both.  So they have no common factors, and that's how you verify you have no common factors. That's one way to verify it.  By and also that idea of successive subtractions.  So let's look at an example here and then I will be quiet and man the machine.  So let's, this is doing exactly, but it would have been a little hard to stretch out 140 black unifix cubes, so you start with 140 and 33. You subtract the smaller and the smaller, and the smaller, and the smaller, and now what's left over is 8.  So eight is now the smaller, so we switch them over, that was when you changed colors, and now we subtract eight, once, twice, three times, four times, and now, we are down to one left over.  So if we get down to a unit, then those things are relatively prime. So that's the idea just with subtraction.  Of course Euclid couldn't actually not have done this. because he didn't write 25 and 8 like that, but he certainly had the idea, and knew what was going on.  And if you check it out, the only things that divide into 33 are 3 and 11, and what divides in here, this is two times seventy, so it is 2 x 2 x 5 x 7, and none of those are 11 and 3, so no common divisors.  SO that's the basic idea of things relatively prime, and this idea of subtracting and then Euclid is going to actually leverage that idea into something even more interesting.  

>> Dr. Slough:
I think I'll just stay here. 

>> Dr. Andrews:
All right, I'll just go over here then.

>> Dr. Slough:
Ok, so that's the idea of relatively prime. Now we want to ramp things up just a little bit, but not much, so again, we start with two numbers, two whole numbers, in this case 1035 and 759 and using the language of Euclid, we are looking for a common measure, which today we call it a common divisor, but we want the greatest common measure, or today's language, the greatest common divisor.  So, lets just think about this for a second. So let's forget Euclid. Just try some things. Well, how about 3?  Is three a divisor of both? Well, sure enough. So that's a candidate for an answer. If you wanted to take this back a little bit, you could say well how about one?  Should one be an answer? Because one divides anything, so one is certainly common, but is it the biggest? No, three is bigger, can you find one that is bigger yet?  Well, with a little bit of work, it's not hard to see that 23 divides both of them, so there's a bigger candidate for the answer.  Is that the biggest one though?  Well, no. So you can find one bigger, 69, divides both of them.  Is that the biggest one?  Well, I can't say without a little bit of effort, but it turns out that it is, and one way to see that it is, is to produce the factorization, prime factorization of each of them, so 3 x 3 x 5 x 23 that product is 1035, 759 same thing, takes a little bit of work, this would take, I said a little bit of work, but I need to tell you that my background is computer science, and for computer science, these numbers aren't even worth thinking about.  These are too small.  So the kinds of numbers that we sometimes think about they've got thousands of digits. Now if you  take a number that's got a thousand digits, and try this sometime when you are bored, and try to factor that number, you are going to have a hard time doing that, unless that number is a very special, you've chose it very specially, but just pick a random 1000 digit number, you are going to have a hard time factoring that. And when I say you, it's not just you, because computers would have a hard time doing the same thing. It would take them a long, I mean, a computer could do it, but it would take a long time.  So, the idea here is, it goes a little bit beyond the mathematics, because we don't want necessarily just the answer, but we want to be able to get it quickly without too much work, whatever "too much" might mean.  So, as we like to say in math, it turns out that this is a horrible idea to get the answer, if you are interested in efficiency, just factoring.  So, again, let's ignore Euclid and just try this ourselves, you might think that we are a little smarter than Euclid.  Here's a way, a horrible way, it turns out, look at the answer, but not anytime too soon. Again, imagine that these two numbers are a thousand digits each. SO here,'s my silly way of doing this.  So you take the samller of the 2, and you think to yourself, well, maybe this is the answer.  It certainly couldn't be any bigger than that number. Let's take two small numbers, so if I said 18 and 39, the answer can't be any bigger than 18, the smaller of the two, because if I tried to get anything bigger than 18, it wouldn't divide 18, itself.  So, that's the biggest it could be. And then I just sort of worked my way down, and then looking for the first one that I find that divides both. That will certainly work, in every sense of the word, if it's correct, but it's almost an exaggeration to say this is very labor intensive. That's an over-simplification.  So, why should we ignore Euclid? He's a smart guy, so let's go back and see what he had to say. Now this is exactly, on this slide, this is exactly what Peter was telling us, it's just expressed in the modern language.  So, GCD (Greatest Common Divisor) GCD of X and Y, so there's two a pair of two numbers, and if X is the bigger of the 2, then what you do is you just subtract and you are left with a slightly simpler problem.  Simpler in the sense that at least one of the numbers got smaller, which is what you did just a few minutes ago.  Now the word that strikes fear into every mathematics student, a proof, and for reasons of time, I am actually, you can thank me later, I am actually not going to go through this proof, but I will just say that's it's actually among all proofs, it's among the simpler proofs, and if I just gave you this hint and perhaps a little bit more, I think you could come up with this on your own.  So, why are those two numbers equal?  The basic ideas is you want to show that you've got two numbers that are equal, while each is less than or equal to the other.  And if you can show that both ways, then they have, the only way that both of those facts could exist, is if the two numbers are the same.  Ok, so, as we sometimes see in mathematics, that's left to the reader, left to the reader, that's for you to do.  Now it's actually here, but like I said, I am going to skip it, you can thank me now or thank me later, so let's just quickly skip that.  And here's this same modern statement of Euclid's idea, two numbers X and Y, take the smaller, subtract it from the larger, and throw away the larger, and what you are left with is (turns out) the answer to that simpler problem is the same as the answer to your original problem. That's an idea that pervades a lot of mathematics, you take one problem and you turn it into something that's simpler in some sense and you work down the simpler problem. The great thing about this is it just keeps iterating that idea.  Keep turning it into a simpler and simpler problem.  So, if you believe that, and we haven't really given you a reason to believe it, but Euclid proved it, and I skipped it, but it's probably the worlds simplest algorhythm method to carry out, so if you know how to subtract, and you know how to compare two numbers, anybody can do this, including a computer.  Computers are good at comparing two numbers and they are certainly good at subtracting, and everyone in this room could easily do this. Even for a thousand digit numbers. Well you'd get tired of doing it, but you could do it in principle. SO here's the same sort of thing we did before, subtract, now, the X column I am always making sure I put the bigger number, so if the subtraction turns out to disrupt that order, then I'll just flip them around.  Subtract, sbutract, now again, I disrupted the order, so let's put it back so that I've got the biggest one in the X column, subtract, again, the order is disrupted, slide out, subtract, subtract, now you  could stop here according to Euclid and he would recognize that 69 measures 69 and there's your answer, 69 must the the greaster common measure or the greatest common divisor of that original pair.  If you didnt recognize that, you could always subtract and you get to zero, you'd better stop.  So, that's it.  Now, that of course takes advantage of what we know about numbers and arithimetic, which that is as Dr. Andrews said, wans't available to Euclid, so here's essentially the same thing you did with the manipulatives.  At pretty much as Euclid would do it. SO, here is just a small example, 30 and 21, so I've measured out on the left, 30 units, that's to the right of that, 21 units, and what do we do?  We have to subtract, but how do you subtract? See, you get your calipers from that painting that we saw, and you mark it off. So there's one, and you try to mark it off the second time, what happens? It doesn't fit.  So you've got a piece left over. Now, what happens? You take the left over piece, and you move it off, and so this left over piece is exactly this left over piece, and then you just slide this over.  So that's one application of what we today would call Euclid's rule.  And so now I've got two pairs of numbers, this pair and this pair, and Euclid would say the answer to the question we have in mind, is exaclty the same. Doesn't matter which one you pick, this one or this one.  WEll, why wouldn't you pick the one on the right, it's simpler?  And if you wanted to put numbers to the blacks of course, it's not hard to do. What have we got here? We've got on the right we've got the 21 that we started with, and then this is the leftover piece, 30 minus 21, 9.  And do it again, so you measure you measure and there's leftover piece.  And you take the leftover piece, and you lop it off, and move it over there with the other length, and now we've got three pairs, and according to Euclid, all three of them have the same answer.  Same greatest common divisor.  So, you get to pick, which one would you like to work on?  Well, of course you want to take the simplest one. Simple means smaller.  So you measure once, twice, three times and it fits exactly, and when it fits exactly you are done.  So the small one measures the big one, and in thise case, three times, and this isn't the proof of anything but just for fun, let's put the original two numbers up there, and lets' at least make sure that this is the answer.  That better measure each of them.  THis doesn't prove that it's the biggest measure, but at least it better measure, and sure enough you mark it out and you can see that it does.  Ok, now, you can take that idea and this idea of measuring, measuring off so many times, why keep subtracting, why not just do it in one operation and be done with it? So, repeated subtraction, as I think everyone here knows, is just, I call it forth grade division.  I don't know if that is really accurate, could be third grade, where did we learn that?  Quotient the remainder is basically what we are talking about.  SO, here's the same idea expressed in modern notation, that essentially comes from Euclid. So if you have an original pair of numbers, x,y and you want the greatest common measure, greatest common divisor, what you can do is you can make a simpler problem by doing not subtraction any more, that's too much work, let's just do one division, so this is the modern notation that perhaps some of you have seen before, (X mod y) what that means is you divide x by y and you take the remainder, just like we did in well, I'm going to say, 4th grade. But it might be third grade where you went to school.  And of course it doesn't matter which way you arrange them here, whether it's this way, or the other way around, it's exactly the same, and let see an example of this.  So, you could do this the old way, that I showed you, subtract, subtract, and so forth, but let's use our new-found knowledge.  So we do division.  1035 divided by 759, so again you can think of this geometrically, take this line segment of 1035, measure off 759, how many do you get? Goes in once, we would say in 4th grade, right?  It goes once, with a remainder of 276.  Now what happens? Look at this. So it says, take the second one, slide if over into the first position, so the 759 should come to the x column, what goes here? According to Euclid, the remainder, and the remainder was 276, so we now, you can predict as well as I can show you 759 is going to come down, 276 will appear in the y column.  

But again, now you've got 2 lengths, 759, 276. Take your calipers, mark off 276 as many times as you can, any fourth grader will tell you with a little prodding, that that goes in twice, with a remainder of 207.  What happens next?  276 slides down, the remainder fills in the gap.  276, 207 do it again.  Divide, division is pretty simple.  So, 207 slides down, the remainder comes into place. Do it again. THis time, 69 measures to 207 exactly three times in fact, and so you could either stop there and realize that it measures it, or you could just go ahead and do it, and as soon as you get to a remainder of zero, there's you answer.  This is the algorhythm that basically Euclid gave is in what is called Proposition Two, so Book Seven, Proposition One, talks about two numbers that are relatively prime, and how to determine that. Proposition two, gives us this, and in case your are not sufficiently impressed, let me say it for you.  This fantastic method and it's fantastic for a number of reasons, well, first of all you have to be kind of interested in finding the greatest common divisor, assuming that is the case, this is fantastic, because if you know how to divide, it turns out that this not only gives you the correct answer, but it gives you the answer in a I'm going to say relatively small amount of work.  Relatively few number of divisions.  Donald Canuth, who is sort of the modern day founder of this study of algorhythms, basically has told us that this really is among the worlds oldest algorhythms that we know about.  If you wanted to, and it's not hard, and I won't go through the details, it wouldn't be hard to write a computer program to basically automate what I just showed you.  This is an exact transcription of one version of a computer program that would do that, and if you look, even if you know nothing about computer programming, you can look at this, and you can look at the modern day transcription of Euclid, and you can just see how similar things are.  Look at this, return GCD, Y, this looks kind of bizarre, X% Y, but in computer language, java, that simply means 4th grade division, give me the remainder.  

Fast forward to the 1800' and there was a french I think he was a mechanical engineer, and he basically said, now wait a second, I know about this method for finding this Greatest Common Divisor, but he stated in a much more precise way than I did just a minute, just how good this is. And it basically, what's important is this part right here.  It takes at most 5k steps, and what is k? K is the number of digits involved, and if you think back to the problem that I was telling you about, k is what? Well, for all of the simple examples, K is, what did we do? Four, we had a four digit number I think, three digit number, but the kinds of numbers that people that study algorhythms would be interested in, is today, 1,000, 2000, maybe a million, so think, just think how good this really is, what this is telling us. If we had two numbers that are roughly on the scale of a million each, in the millions, so K is what? 6? So roughly in a handful of steps, 5 x 6, you can get the answer.  So think back to that what I called brute force method, just think how hard that would be relatively speaking, if I took two numbers in their millions, and I say, well, let's start at the top and work my way down, I am going to be here all day, and that same idea applies to computers, you can get a computer, if you can provide a computer with an algorhythm that has a relatively small number of steps, that means you can get the answer quickly.  Ok, so that was the 1800's, now I am going to take you fast forward through a couple more centuries.  I am going to skip, basically skip over a lot of details here, and you can thank me later. This isn't hard, what I am skipping over, but it's more than what we want to do today.  So this is not Euclid, this is again, a result from the French mathematician in the 1800's so quite a few centuries have gone by, but basically the claim is that you can take this pair, x and y, you can find the greatest common divisor, d, but not only that, you can find this other pair of numbers, kind of magical, that when you combine them in this way, it adds up to the greatest common divisor. And as we like to say in mathematics, sometimes, "it turns out" that to find those somewhat magical numbers, is not that far removed from doing what Euclid said. So basically take the same kind of table, you expand it a little bit, and you get this nice result.  I say it's nice, because it turns out to have a very practical application.  And fast forward another couple centuries, and you find that people are quite interested in the internet these days, and people like to communicate on the internet, but not everything is intended to be public.  So, for example, if I make a purchase on the internet, and I type in my credit card number, I kind of like to believe that that credit card number isn't being seen by the entire world.  Well, in the late 1970's now it took three computer scientists to come up with this idea, but it got this, what I think, most people would say, this clever idea and it all goes back to Euclid.  And it's a question of if I send some information over the internet, and maybe someone is in some sense "listening" they can see what I am sending, I want to send it in a way that even if someone else saw it, it would just look like jibberish. So that's the idea of today what we call incryption. So I, it's like sending a secret message back when you were in the third grade. You had your cracker Jacks decoder ring, and your friend had the same decoder ring, and you would send this secret message.  It's the same kind of thing except that if you do this in a cracker jack's way, and you send the message like your credit card number over the internet, that's not so good, because everybody knows about the cracker jacks and the decoder ring, and with little trouble you can figure it out.  So that's not good. SO you need a way to send something that looks like jibberish that on the other end somebody else can decode, so there's basically two kinds of things going on here, encryption, taking good stuff and turning it into jibberish, and decryption, taking the jibberish and turning it back into what it started. So, I could talk for an hour more at least, probably two hours, just on this slide, but I am not going to do that, but I do want to just mention that there's a key component to how all this works, is mathematical and it relies on this extended Euclid algorhythm. There's also this other idea, which isn't completely related to Euclid other than the fact that of course he kicked off the study of prime numbers, which for many years, people thought that was just an amusing mathematical recreational kind of thing right? WHo carea about prime numbers?  Well, it turns out this is a prime example, it turns out that prime numbers have practical applications, and this is one of them.  So, a couple of things here.  Go back to Euclid.  Number one, prime numbers, number two, this idea of finding the greatest common divisor.  So, even though I didn't pick the title of this symposium, I think it was a perfect match to Euclid through the centuries, going all the way back to roughly 300 BCE, to essentially today, and it all sorta of hangs together in a rather nice way, and so these things that we see now in books that you might be tempted to say, oh well, this is an interesting recreational thing, but it is not good for anything, you'd be surprised.  So, hats off the Euclid.

[Applause]

>> Dr. Wahby:
And hats off to our distinguished speakers and we have other classes to go to, but if you have a question about anything this morning, you can ask of our speakers, otherwise, go in peace and see you next time.